1. Technical Field
A method and an apparatus for deciding on the compliance of cells at an input port of a switch is used to determine whether cells arriving at a switching device have to be considered compliant or non-compliant which result is useable as a basis for the decision whether that cell shall be discarded or may be accepted.
2. Prior Art
In the field of transportation of information via fixed-length cells, switches are used which connect a plurality of incoming connection lines to a plurality of output connection lines in that they forward cells arriving on the incoming connection lines to the output connection line to which said cells are heading. Since such switches are limited in their capacity to handle cells without cell loss, each incoming line is assigned a maximum cell deliverance rate, also called allocated bandwidth. As long as all senders stay within the limit defined by the respective allocated bandwidth, the switch is designed to handle the cells without risk of loss of information. For correct function, a mechanism is used to determine for each connection the currently used bandwidth. If a sender exceeds its bandwidth limit, e.g. a control signal may be sent upstream to the sender to make him throttle his output cell speed. The correct determination of the currently used bandwidth is hence important for guaranteeing quality of service for all connections. Known mechanisms use a time counter which is used as basis for the determination of the arrival time of incoming cells. A theoretical arrival time is calculated for a next cell expected to arrive on the same connection line as a preceding cell. A generic cell rate algorithm, short GCRA, is then performed which compares the arrival time of this next cell with its theoretical arrival time, also called TAT. The GCRA generally performs two actions: Upon arrival of a cell it decides whether an arriving cell is considered compliant or non-compliant and it afterwards calculates the new theoretical arrival time TAT. The known principles of GCRAs are described in the ITU Recommendation I.3711 of the ITU Telecommunication Standardization Sector, March 1995. The GCRA is also known as the leaky-bucket algorithm which exists in various modifications. An overview over the leaky-bucket principle can be found on the Internet the address http://www-kr.cisco.com/univercd/data/doc/lightstr/r2xe2x80x942/sys_over/traffic.htm.
In U.S. Pat. No. 5,418,777 a modified leaky-bucket method is disclosed for a message transmission system wherein a message cell stream is asynchronously transmitted and is carrying message cells for a plurality of virtual connections. The message cell rate for every virtual connection is being monitored, the shortest allowable timing between two message cells belonging to the same virtual connection being represented by the quotient of two numbers.
U.S. Pat. No. 5,224,092 describes a method for controlling a flow of data cells into a plurality of asynchronously time-divided transmission channels with a single admission switch for transmission in the channels with reference to the state of a plurality of count values. Therein the incrementation or decrementation of a number of variables is used, which variables are processed to produce a number of assessment signals which are then converted by further processing into a control signal that is used to accept or not accept data cells. Another thereto pertinent patent is U.S. Pat. No. 5,224,091 which is related to a method for monitoring a transmission system which comprises a plurality of virtual asynchronously time-shared transmission channels via which a data flow can be transmitted.
U.S. Pat. No. 5,509,001 describes an apparatus for controlling cells which are to be input to an ATM switch. The apparatus includes a periodic calculation circuit for periodically changing the number of cells for each of different calls and a control part for determining whether the cell stored in a buffer circuit should be output to the ATM switch or discarded.
An accounting system and method for an asynchronous transfer mode network is described in U.S. Pat. No. 5,623405.
A problem arises due to the fact that the counting range of such counters is in real hardware always limited. When reaching the highest possible reading, the counter therefore wraps to its lowest reading and starts counting again. Therefore, counter readings after a counter wrap are lower than some counter readings before. This leads to cell mishandling and mistreatment of senders. More precisely, the time counter wrap can lead to situations where cells are considered compliant although they are non-compliant and also to cells being considered non-compliant although they should be considered as compliant. With other words, if the time counter has a wrap either while waiting for a cell or before the next TAT, the GCRA result may be wrong.
It is an object of the invention to provide an apparatus and also to provide a method which avoids the above disadvantage in that it is designed to determine correctly the actually used bandwidth on connection lines on which cells are arriving. This is achieved in that the wraps of the time-counting means are monitored to determine whether a wrap occurred, the result of that determination being useful for deciding whether the theoretical arrival time has a valid value to be compared with the arrival time of an arriving cell.
In the dependent claims additional improvements and variations of the apparatus and of the method are contained therein.
A second comparison means for comparing the reading of the wrap-counting means at the first arrival time with the reading of the wrap-counting means at the second arrival time is a practical and simple solution for finding out the difference in the number of windows in which the first and the second cell arrived. This difference is an important variable for correctly determining the used bandwidth on that connection.
For easily finding out the number of the window in which the theoretical arrival time lies, the reading of the wrap-counting means at the theoretical arrival time can be used.
A practical solution for keeping the memory of the arrival times is to store the reading of the time-counting means at the second arrival time and at the first arrival time. When the storing places are arranged in form of a shift register, upon arrival of a new cell, the storage of the new arrival time will automatically effect the conversion of the arrival time of the previous cell which up to then has been the second arrival time, to the then valid first arrival time. This automatism is very simple and therefore needs not much dedicated logic.
State-determination means can be used to initiate on a timely regular basis with a predetermined repetition period a process which effects an artificial second arrival time for which the reading of the wrap-counting means is determined. This reading together with the reading of the wrap-counting means at the theoretical arrival time is usable for the determination whether a wrap occurred between the theoretical arrival time and the artificial second arrival time. This is a background process which even leads to correct cell-handling when the wrap-counting means has a wrap itself. The result of the background process can be used for setting a validity flag which indicates if the theoretical arrival time is valid for the next arriving cell or not.
For obtaining the maximum precision of the cell rate determination process, the repetition period should be chosen at maximum the time between two wraps of the time-counting means multiplied with the maximum reading of the wrap-counting means minus 2. Then it is guaranteed that, if the background process has been applied for one connection in the window where the previous cell arrived or in the window after that window, for the same connection the background process at latest is performed again before the wrap-counting means has reached one of the numbers of these windows again. Hence, every cell arrival constellation is treated fair.
If the artificial second arrival time lies one wrap event after the first arrival time and the theoretical arrival time, and/or if the artificial second arrival time lies two or more wrap events after or at least one wrap event before the first arrival time and the theoretical arrival time and/or if the artificial second arrival time lies one or more wrap events after the theoretical arrival time which lies one wrap event after the first arrival time, a type of situation has occurred in which the TAT is no longer valid such that the arrival time of the next arriving cell need not be compared with that TAT. Therefore, the validity flag can be reset which makes clear that the TAT shall not be used for comparison, or that the comparison may be performed but its result will not be used. The classification of the various constellations of the first arrival time, the second arrival time and the TAT provides a basis for a simple case-determining scheme which simply finds out the current case type which result can be used for the decision whether a comparison of the second arrival time with the TAT makes sense or not. In the above given cases, the comparison can be renounced. The validity flag serves as a sort of one-bit memory for that conclusion.
Upon arrival of the arriving second cell, the validity flag can then be tested on its value. If it is reset, then the arriving second cell can automatically be considered compliant. With this method, the compliance of the arriving second cell can very easily be determined.
Upon arrival of the arriving second cell, if the theoretical arrival time and the second arrival time both lie one wrap event after the first arrival time, and/or if the second arrival time, the first arrival time and the theoretical arrival time are all together not separated by a wrap event, the second arrival time and the theoretical arrival time shall be compared for deciding whether the second arriving cell is considered compliant or non-compliant. The comparison is performed with a reset carry flag, or without using the carry flag. The carry flag is set when the time-counting means has a wrap.
Upon arrival of the arriving second cell, if the theoretical arrival time lies one wrap event after the first arrival time and the second arrival time, the second arrival time and the theoretical arrival time may be compared for deciding whether the second arriving cell is considered compliant or non-compliant. Therefor, again the carry flag should be used. This carry flag shall be reset every time, when a cell has been handled, i.e. it has been decided on its compliance.
Upon arrival of the arriving second cell, if the second arrival time lies one wrap event after the first arrival time and the theoretical arrival time, and/or if the second arrival time lies two or more wrap events after or at least one wrap event before the first arrival time and the theoretical arrival time and/or if the second arrival time lies one or more wrap events after the theoretical arrival time which lies one wrap event after the first arrival time, the arriving second cell can be considered compliant. Again, a simple case determination simplifies the process of cell-handling in that it recognizes the constellation of times. This process on one hand is faster than a process which uses a comparison procedure and on the other hand is fairer because the risk of mistreatment is reduced or even avoided totally.
The period of time which the time counter, hereinafter called time-counting means, can count without having a wrap is hereinafter called a window.
A window counting means is used which counts the number of wraps. Hence, the actual real time can be modeled more exactly by using the actual time-counting means state and the window counting means state. However, also the window counting means has a limited range and a wrap would again result in wrong GCRA cell handling. The window counting means is more or less only a prolonged time-counting means. The prolonged time can be used to run a background process which determines the situation in that it tests the validity of the theoretical arrival time TAT for the next expected cell.
This is accomplished in that the background process simulates the arrival of a cell for each connection sequentially and determines the validity of the TAT but does not run a GCRA process which would be performed if a real cell arrived.